package q96_numTrees;

public class Solution_1 {
    /**
     * 此题从表面上看 与动态规划的相关性较低
     * 我们可以这样分析 对于 dp[i] 代表有i个节点的时候能够构建的搜索树数量
     * 我们利用n = 3的情况来分析递推的状况 n为3的时候 有三种情况
     * 1 头节点是1 那么意味着两个剩下的节点只能够在它右边
     * 2 头节点是2 那么两个剩下的节点分别分布在两侧
     * 3 头节点是3 那么只能在左边
     * 那么递推的状况就出来了 对于头节点是1的时候 右边的两个节点的分布 实际上是跟n = 2的时候类似的 只不过是从1、2 变成了 2、3
     * 所以这个时候 情况1的数量应该是dp[0] * dp[2]
     * 同理可以推出 剩下两种情况是 dp[1] * dp[1] 和 dp[2] * dp[0]
     * 所以递推公式也就是 for j in i : (dp[i] = dp[i] + dp[i - j] * dp[j - 1])
     * 唯一要注意的是dp[0] = 1 也就是没有节点的时候 我们认为为1种情况
     * @param n
     * @return
     */
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        // Arrays.fill(dp, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = dp[i] + dp[i - j] * dp[j - 1];
            }
        }

        return dp[n];
    }
}
